package com.example.algorithm.no0088.solution;

import com.example.algorithm.no0088.Solution;

/**
 * @Description 解答-合并两个有序数组
 * 双指针 / 从后往前
 * 时间复杂度 : O(n + m)。
 * 空间复杂度 : O(1)。
 * @ClassName MapSolution
 * @Author Administrator
 * @Date 2020/5/20 10:26
 * @Version 1.0.0
 */
public class SolutionImpl2 implements Solution {
    @Override
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // two get pointers for nums1 and nums2
        int p1 = m - 1;
        int p2 = n - 1;
        // set pointer for nums1
        int p = m + n - 1;

        // while there are still elements to compare
        while ((p1 >= 0) && (p2 >= 0))
            // compare two elements from nums1 and nums2
            // and add the largest one in nums1
            nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];

        // add missing elements from nums2
        System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
    }
}
